/*  slfllmul.cpp  by K.Tsuru  */
// function ID = 209  DRADIX , BRADIX
/************************************************************************
SLong class
It returns m*n.
When the number of figures is equal to 2^p+a,where a is small, the direct
use of FFT multiplication needs a processing time twice over in comparison
with 2^p figures. Then it is splited into 2^p and "a" figures.
*************************************************************************/
#ifndef SN_H
#include "sn.h"
#endif
static const char* const func = "LLMult";
// void (*SLong::pfHHMult)(const SLong& x, const SLong& y, SLong& z) = NULL; // deleted since version 2.192
bool SLong::usesKaratsuba_HH_Mult = true;

/*
|m| >= |n| > 0
For the simplicity of algorithm the longer number is taken as the multiplicand.
*/
SLong LLMult(const SLong& m, const SLong& n){
// make sin table on memory
#if USES_SIN_TABLE_FFT
    if(FFTSineTableSize() == 0) MakeSinTable(FFT_MAX_SIZE_BITS);
#endif

    if(!m.FFTUse()) return NLLMult(m, n);
    if( m.Head() < n.Head() ) return LLMult(n, m);  //n is longer.
// |n| == 1 ?
    if(n.IsOne()){
        if(n.Sign() > 0) return m;  // n == 1
        return -m;                  // n == -1
    }
//It checks the signs.
    int sgn = m.Sign(209)*n.Sign(209);
    SLong result(m.Type(), 0);      // figure.size() = 0;
    if(!sgn){   // m = 0 or n = 0
        result.SetZero();
        return result;
    }
    uint mh = m.aHead, mt = m.aTail, nh = n.aHead, nt = n.aTail;
    uint m_fig = mh + 1, n_fig = nh + 1;    // the numbers of figures of m and n
/*
It checks the overflow error.
The size of result is less than or equal to (m_fig+n_fig),
e.g. 10*10 = 100, 99*99 = 9801
Mar 26, 2001
  I changed the condition below from "(m_fig + n_fig) >= m.MaxSize()".
*/
    if( (m_fig + n_fig) > m.MaxSize() ) m.SetError( m.OVERFLOW_ERR, func, 209);
#if 1
//It can be reduced into (multi-precision number)*(short one)?
// ver. 2.17
    if( mh - mt < 2 ){  // m is short less than two figures. m=X*R^mt(R:radix)
        ulong d = (ulong)m.figure(mt);
        if(mh > mt) d += m.Radix()*(ulong)m.figure(mt+1);
        if( d <= n.SlOpMaxValue() ){
            if(d != 1) result = LsMult(n, d);
            else       result = n;  //d==1, m=1*R^mt>1
            result.SetSign(sgn);
            if(mt) result.ShiftArray((int)mt);  //It multiplies by R^mt.
            return result;
        }
        return NLLMult(m, n);
    }

    if( nh - nt < 2 ){  // n is short less than two figures. n=X*R^nt(R:radix)
        ulong d = (ulong)n.figure(nt);
        if(nh > nt) d += n.Radix()*(ulong)n.figure(nt+1);
        if( d <= m.SlOpMaxValue() ){
            if(d != 1) result = LsMult(m, d);
            else       result = m;  //d==1, n=1*R^nt>1
            result.SetSign(sgn);
            if(nt) result.ShiftArray((int)nt);  //It multiplies by R^nt.
            return result;
        }
        return NLLMult(m, n);
    }
#endif
    if(m.Type() != n.Type()) m.SetError(m.RADIX_ERR, func, 209);

//m and/or n is abcd00......0 ?
//mt and nt has number of last zeros.
//A quarter and over of all figures are equal to zero.
    bool mHasManyZero = ( m_fig < 4*mt ) , nHasManyZero = ( n_fig < 4*nt );
    if( mHasManyZero || nHasManyZero){
        SLong M, N;
        if(mHasManyZero && !nHasManyZero){
            result.SLCutOut(M, m, mt, mh - mt +1);
            result = LLMult(M, n);  //recursive call
            result.ShiftArray((int)mt);
            return result;
        }else if(!mHasManyZero && nHasManyZero){
            result.SLCutOut(N, n, nt, nh - nt +1);
            result = LLMult(m, N);
            result.ShiftArray((int)nt);
            return result;
        }
        result.SLCutOut(M, m, mt, mh - mt +1);
        result.SLCutOut(N, n, nt, nh - nt +1);
        result = LLMult(M, N);
        result.ShiftArray( int(mt + nt) );
        return result;
    }

//If n has small figures, a normal method is called.
    if( (nh - nt +1) < m.FFTMinSize()) return NLLMult(m, n);

    uint mf2 = ceilpow2(m_fig), nf2 = ceilpow2(n_fig), fft_sz = 2*mf2;
    uint divN = mf2/nf2;    //a ratio of figures
//If a statement m.HHMultMode(m.hhMultMode); is used, the function KHHMult() is linked.
//  if(m.pfHHMult == NULL) m.pfHHMult = NHHMult;
//In the unit of "nf2" the figures of m and n are diffrent each other.
//m is divided by the figures of n and calculate the product.
    if( (nf2 > 256u) && (divN > 1) ) return DivLLMult(m, n);

//Here (mf2 == nf2) && (m_fig >= n_fig)
//When the upper half of n has small figures.
// Removed on 14 Sep, 2000
//  up_fig = n_fig - nf2/2;
//printf("fft_sz=%u,divN=%u m.Head()=%u, n.Head()=%u\n",fft_sz, divN, m.Head(), n.Head());
//  if((divN==1) && (up_fig < (nf2/16))) return DivTwoPartsLLMult(m, n);

//FFT multiplication
    if( fft_sz <= m.FFTMaxArraySize() ){ //It needs one time.
        m.fftArraySize = fft_sz;
        result.LLMultFFT(m, n, result, m.fftArraySize );
// result = NLLMult(m, n);
    } else {    //It needs some times.
        m.fftArraySize = m.FFTMaxArraySize();
        
        if(m.UsesKaratsubaMult()) result.KaratsubaHHMult(m, n, result);
//      if(SLong::hhMultMode == SLong::Karatsuba_HH_MULT) result.DisKHHMult(m, n, result);
        else result.NHHMult(m, n, result);
//      (*m.pfHHMult)(m, n, result);
    }
    result.fftArraySize = FFTSize(); //decided in LLMultFFT()
    result.SetSign( sgn );
    return result;
}